package demo.niuke.demo2;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {

    public static void main(String[] args) {
        // nums1 = [3,1,2], nums2 = [1,2,3]©leetcode
//        int[] nums1 = {3,1,2};
//        int[] nums2 = {1,2,3};
//        System.out.println(new Solution().minOperations(nums1, nums2));
        // nums1 = [1,1,2,3,4,5], nums2 = [5,4,3,2,1,1]©leetcode
        int[] nums1 = {1,1,2,3,4,5};
        int[] nums2 = {5,4,3,2,1,1};
        System.out.println(new Solution().minOperations(nums1, nums2));
    }
    public int minOperations(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int num = nums2[i];
            map.computeIfAbsent(num, k -> new ArrayList<>()).add(i);
        }
        
        int[] A = new int[n];
        for (int i = 0; i < n; i++) {
            int num = nums1[i];
            List<Integer> indices = map.get(num);
            if (indices == null || indices.isEmpty()) {
                return -1;
            }
            A[i] = indices.remove(0);
        }
        
        int lisLength = computeLISLength(A);
        return n - lisLength;
    }
    
    private int computeLISLength(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int x : nums) {
            int left = 0, right = size;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails[mid] < x) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            tails[left] = x;
            if (left == size) {
                size++;
            }
        }
        return size;
    }
}